{
 "metadata": {
  "kernelspec": {
   "display_name": "Scheme",
   "language": "scheme",
   "name": "calico_scheme_kernel"
  },
  "name": "",
  "signature": "sha256:40ed3b0c6a60a5a6f651260bbbe14902807ff59147eedc7f3d7d9a08a394d12c"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#Lazy Evaluation: Scheme Streams\n",
      "\n",
      "## Douglas Blank\n",
      "## Bryn Mawr College\n",
      "### Programming Languages\n",
      "### Fall 2014"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Arguments to Scheme functions\n",
      "\n",
      "All arguments are:\n",
      "\n",
      "* Evaluated (in some undefined order) prior to calling the function\n",
      "* Passed by value to the function"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Consider:\n",
      "\n",
      "`(f (f2 23) (lambda () 89) 67)`\n",
      "\n",
      "each of:\n",
      "\n",
      "* `(f2 23)`\n",
      "* `(lambda () 89)`\n",
      "* `67`\n",
      "\n",
      "is evaluated before being passed in to $f$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Evaluating, then passing in to the function is called \"eager evaluation\""
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Lazy Evaluation"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can use closures to delay computation!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define L (lambda () (+ 3 4)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "And we can force the evaluation later:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(L)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 44,
       "text": [
        "7"
       ]
      }
     ],
     "prompt_number": 44
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Very similar to the idea of a continuation\n",
      "\n",
      "## Lazy Evaluation:\n",
      "\n",
      "We create some helper functions to create a Domain Specific Language (DSL) inside of Scheme using closures to delay computation. We'll explore `define-syntax` in detail below."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define-syntax freeze\n",
      "    [(freeze ?a) (lambda () ?a)])\n",
      "\n",
      "(define thaw\n",
      "    (lambda (?a)\n",
      "        (?a)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 45
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lazy Evaluation with freeze and thaw"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(freeze (+ 1 2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 46,
       "text": [
        "#<procedure>"
       ]
      }
     ],
     "prompt_number": 46
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define L (freeze (+ 1 2)))\n",
      "(thaw L)\n",
      "3"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 47,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Scheme Stream\n",
      "\n",
      "A stream is composed of an item (thawed) cons-ed onto a (frozen) stream, recursively."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define partial-stream (cons 'a (lambda () 'b)))\n",
      "(car partial-stream)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 48,
       "text": [
        "a"
       ]
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(cdr partial-stream)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 49,
       "text": [
        "#<procedure>"
       ]
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "((cdr partial-stream))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 50,
       "text": [
        "b"
       ]
      }
     ],
     "prompt_number": 50
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A *stream* is composed of an item (thawed) cons-ed onto a (frozen) stream, recursively."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define partial-stream (cons 'a (freeze 'b)))\n",
      "(car partial-stream)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 85,
       "text": [
        "a"
       ]
      }
     ],
     "prompt_number": 85
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(cdr partial-stream)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 86,
       "text": [
        "#<procedure>"
       ]
      }
     ],
     "prompt_number": 86
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(thaw (cdr partial-stream))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 87,
       "text": [
        "b"
       ]
      }
     ],
     "prompt_number": 87
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A stream is composed of an item cons-ed onto a frozen stream, recursively."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define partial-stream (cons 'a (lambda () 'b)))\n",
      "(car partial-stream)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 88,
       "text": [
        "a"
       ]
      }
     ],
     "prompt_number": 88
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "((cdr partial-stream))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 89,
       "text": [
        "b"
       ]
      }
     ],
     "prompt_number": 89
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "But that is only a partial stream, because the cdr is itself not a stream.\n",
      "\n",
      "Streams\n",
      "Goal: create tools and data structures to make an infinite stream built on freeze and thaw.\n",
      "\n",
      "Something like a list, but infinite.\n",
      "\n",
      "Need something similar to cons, car, and cdr...\n",
      "\n",
      "## Macros"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Before we proceed, we need to explore the idea of a _macro_.\n",
      "\n",
      "A _macro_ is a process that manipulates concrete syntax. Thus, it just manipulates the text of the code.\n",
      "\n",
      "In Scheme, we use `define-syntax` to create macros. \n",
      "\n",
      "Consider the problem of timing the running of an expression. You need to start a clock before it runs, evaluate the expression, get the stop time, print the time taken, and return the results."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define-syntax time-it\n",
      "    [(time-it ?expr)\n",
      "     (let ((start (current-time))\n",
      "           (result ?expr))\n",
      "       (printf \"The expression took ~a seconds~%\" (- (current-time) start))\n",
      "       result)])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 100
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(time-it (+ 1 2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The expression took 0.000684022903442 seconds\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 101,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 101
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(import \"time\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 102,
       "text": [
        "(time)"
       ]
      }
     ],
     "prompt_number": 102
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(time-it (time.sleep 2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The expression took 2.00317406654 seconds\n"
       ]
      }
     ],
     "prompt_number": 103
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Macros to create Streams"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The heart of what follows is a re-imagined `cons$`. We \"hide\" a freeze inside of it:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define-syntax cons$\n",
      "    [(cons$ ?a ?b)\n",
      "     (cons ?a (freeze ?b))])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Car and cdr can be defined as normal functions:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define car$ car)\n",
      "\n",
      "(define cdr$\n",
      "    (lambda (stream)\n",
      "        (thaw (cdr stream))))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 56
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Scheme Streams"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define X (cons$ 'a 'b))\n",
      "(car$ X)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 57,
       "text": [
        "a"
       ]
      }
     ],
     "prompt_number": 57
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(cdr$ X)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 58,
       "text": [
        "b"
       ]
      }
     ],
     "prompt_number": 58
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define long-time\n",
      "  (lambda (item)\n",
      "    (time.sleep 5)\n",
      "    item))\n",
      "\n",
      "(define X (cons$ 'a (long-time 'b)))\n",
      "(car$ X)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 98,
       "text": [
        "a"
       ]
      }
     ],
     "prompt_number": 98
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(cdr$ X)\n",
      ";; ... long time passes"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 99,
       "text": [
        "b"
       ]
      }
     ],
     "prompt_number": 99
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Infinite Stream of Ones"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Consider making an infinite stream of ones. Infinite? Sure!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define ones (cons$ 1 ones))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 61
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(car$ ones)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 62,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 62
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(cdr$ ones)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 63,
       "text": [
        "(1 procedure <function b_proc_1_d at 0x7f09aaac7c08> ((lexical-address-aexp 1 173 ones (\"In [61]\" 1 23 23 1 26 26))) () #<environment>)"
       ]
      }
     ],
     "prompt_number": 63
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(car$ (cdr$ ones))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 64,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 64
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(car$ (cdr$ (cdr$ ones)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 65,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 65
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Tools for Streams"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define get$\n",
      "    (lambda (n stream)\n",
      "        (if (= n 0)\n",
      "            '()\n",
      "            (cons (car$ stream) \n",
      "                  (get$ (- n 1) (cdr$ stream))))))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 66
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(get$ 10 ones)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 67,
       "text": [
        "(1 1 1 1 1 1 1 1 1 1)"
       ]
      }
     ],
     "prompt_number": 67
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Integers"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define integers-from\n",
      "    (lambda (n)\n",
      "        (cons$ n (integers-from (+ n 1)))))\n",
      "\n",
      "(define integers (integers-from 0))\n",
      "\n",
      "\n",
      "(get$ 10 integers)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 68,
       "text": [
        "(0 1 2 3 4 5 6 7 8 9)"
       ]
      }
     ],
     "prompt_number": 68
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Integers\n",
      "\n",
      "We can think of it looking like:\n",
      "```\n",
      "(0 . (1 . (2 . (3 . (4 . #<procedure>))))\n",
      "```\n",
      "but these cdr's don't exist until they are evaluated.\n",
      "\n",
      "Some have supposed that quantum mechanics' collapsing wavefunction is similar to lazy evaluation.\n",
      "\n",
      "### Nature's Lazy Evaluation\n",
      "\n",
      "\"To put it in most simple terms, nature doesn't decide certain intrinsic properties of elementary particles until they are observed! This is in some sense similar to computer languages supporting functional programming paradigms, where an infinite array can be defined. Access to any element in the array is dynamically computed to return the value, as practically, it's not possible to store an array with infinite elements. Nature seems to do the same.\"\n",
      "\n",
      "<a href=\"http://amitpcgupta-physics.blogspot.com/2012/08/natures-lazy-evaluation-algorithm.html\">natures-lazy-evaluation-algorithm</a>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Schr\u00f6dinger's cat"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Fun with Streams!\n",
      "\n",
      "Adding two streams together:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define add$\n",
      "    (lambda (s1 s2)\n",
      "        (let ((h1 (car$ s1))\n",
      "              (h2 (car$ s2)))\n",
      "          (cons$ (+ h1 h2) \n",
      "                 (add$ (cdr$ s1) (cdr$ s2))))))\n",
      "\n",
      "(define twos (add$ ones ones))\n",
      "(get$ 10 twos)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 70,
       "text": [
        "(2 2 2 2 2 2 2 2 2 2)"
       ]
      }
     ],
     "prompt_number": 70
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Fibs\n",
      "\n",
      "Notice: \n",
      "```\n",
      "      (0  1  1  2  3  5  8 13 21 ...\n",
      "      (1  1  2  3  5  8 13 21 34 ...\n",
      " +    -------------------------------\n",
      " (0 1  1  2  3  5  8 13 21 34 55 ...\n",
      "```\n",
      "    \n",
      "If we assume the fibs exist, then `add$` them to the `cdr$` of the fibs and start with 0, 1 then we get the fibs."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Fun with Recursive Streams?!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define fibs\n",
      "  (cons$ 0 \n",
      "         (cons$ 1 \n",
      "                (add$ fibs \n",
      "                      (cdr$ fibs)))))\n",
      "\n",
      "(get$ 10 fibs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 72,
       "text": [
        "(0 1 1 2 3 5 8 13 21 34)"
       ]
      }
     ],
     "prompt_number": 72
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### multiply$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define combine$\n",
      "  (lambda (op)\n",
      "    (lambda (s1 s2)\n",
      "      (cons$ (op (car$ s1) (car$ s2))\n",
      "             ((combine$ op) (cdr$ s1) \n",
      "                            (cdr$ s2))))))\n",
      "\n",
      "(define multiply$ (combine$ *))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 35
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Factorials\n",
      "\n",
      "Notice that:\n",
      "```\n",
      "Facts:     (1 1  2   6  24  120   720  5040  40320 ...\n",
      "Nats:      (1 2  3   4   5    6     7     8      9 ...\n",
      "Multiplied: ---------------------------------------\n",
      "            1 2  6  24 120  720  5040 40320 362880 ...\n",
      "```\n",
      "Almost the Factorials!\n",
      "\n",
      "1. Assume that a stream exists\n",
      "1. Do something with it that (almost) gives you the stream\n",
      "1. Adjust the first elements to give you the stream\n",
      "\n",
      "\n",
      "Factorials"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define facts \n",
      "    (cons$ 1 \n",
      "           (multiply$ facts \n",
      "                      natural-numbers)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Factorials"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define facts (cons$ 1 (multiply$ facts natural-numbers)))\n",
      "\n",
      "(define !\n",
      "    (lambda (n)\n",
      "        (nth n facts)))\n",
      "\n",
      "(define nth\n",
      "    (lambda (n stream)\n",
      "        (cond\n",
      "            ((= n 0) (car$ stream))\n",
      "            (else (nth (- n 1) (cdr$ stream))))))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "map$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define map$\n",
      "    (lambda (f stream)\n",
      "        (cons$ (f (car$ stream)) \n",
      "               (map$ f (cdr$ stream)))))\n",
      "\n",
      "\n",
      "(get$ 10 (map$ (lambda (n) (+ n 1)) ones))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 73,
       "text": [
        "(2 2 2 2 2 2 2 2 2 2)"
       ]
      }
     ],
     "prompt_number": 73
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "(define the-empty-stream (cons$ '() the-empty-stream))\n",
      "\n",
      "(define null$?\n",
      "  (lambda (stream)\n",
      "    (null? (car$ stream))))\n",
      "\n",
      ";; filter$\n",
      "(define filter$\n",
      "  (lambda (f stream)\n",
      "    (let ((item (car$ stream)))\n",
      "      (cond\n",
      "        ((null$? stream) the-empty-stream)\n",
      "        ((f item) (cons$ item (filter$ f (cdr$ stream))))\n",
      "        (else (filter$ f (cdr$ stream)))))))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 79
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Primes?\n",
      "```\n",
      "(2 . (stream with all divisible by 2 removed))\n",
      "\n",
      "(2 . (3 . (stream with all divisible by 2 and 3 removed))\n",
      "\n",
      "(2 . (3 . (5 . (stream with all divisible by 2, 3, 5 removed)))\n",
      "```"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Sieve of Eratosthenes"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(define sieve\n",
      "  (lambda (stream)\n",
      "    (cons$ (car$ stream)\n",
      "           (sieve (filter$ \n",
      "                     (lambda (x) (not (= (% x (car$ stream)) 0)))\n",
      "                     (cdr$ stream))))))\n",
      "\n",
      "(define primes (sieve (integers-from 2)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 83
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(get$ 10 primes)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 84,
       "text": [
        "(2 3 5 7 11 13 17 19 23 29)"
       ]
      }
     ],
     "prompt_number": 84
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}